/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode091 
 * @author      : ganwei 
 * @date        : 2020年5月8日
 * @Description : Leetcode091 复原IP地址
 */
public class Leetcode0091 {
	List<String> result = new ArrayList<>();
	List<List<Integer>> resultdot = new ArrayList<>();
    /**
     * -解题思路，回溯剪枝
     */
	public List<String> restoreIpAddresses(String s) {
		backtrack(s.length(), new ArrayList<Integer>(),1);
		genIp(s);
        return result;
    }
    
	public void backtrack(int n,List<Integer> li,int index){
		if(li.size() == 3){
			resultdot.add(new ArrayList<Integer>(li));
			return;
		}
		for(int i = index; i < n; i++){
			li.add(i);
			backtrack(n,li,i+1);
			li.remove(li.size()-1);
		}
	}
	
	public void genIp(String s){
		for(List<Integer> l : resultdot){
			StringBuilder sb = new StringBuilder();
			/*
			System.out.print(l.get(0));
			System.out.print(l.get(1));
			System.out.print(l.get(2));
			System.out.println();
			*/
			String ip1 = s.substring(0, l.get(0));
			//System.out.println(ip1);
			if(ip1.length() > 3){
				continue;
			}
			int ipi1 = Integer.valueOf(ip1);
			if(ipi1 < 0 || ipi1 > 255 || (ip1.length() > 1 && ip1.substring(0,1).equals("0"))){
				continue;
			}
			String ip2 = s.substring(l.get(0),l.get(1));
			if(ip2.length() > 3){
				continue;
			}
			int ipi2 = Integer.valueOf(ip2);
			if(ipi2 < 0 || ipi2 > 255 || (ip2.length() > 1 && ip2.substring(0,1).equals("0"))){
				continue;
			}			
			
			String ip3 = s.substring(l.get(1),l.get(2));
			if(ip3.length() > 3){
				continue;
			}
			int ipi3 = Integer.valueOf(ip3);
			System.out.println(ipi3);
			if(ipi3 < 0 || ipi3 > 255 || (ip3.length() > 1 && ip3.substring(0,1).equals("0"))){
				continue;
			}				
			
			String ip4 = s.substring(l.get(2),s.length());
			if(ip4.length() > 3){
				continue;
			}
			int ipi4 = Integer.valueOf(ip4);
			if(ipi4 < 0 || ipi4 > 255 || (ip4.length() > 1 && ip4.substring(0,1).equals("0"))){
				continue;
			}			
			sb.append(ip1).append(".").append(ip2).append(".").append(ip3).append(".").append(ip4);
			result.add(sb.toString());
		}
	}
	
    public static void main(String[] args){
    	Leetcode0091 l091 = new Leetcode0091();
    	l091.restoreIpAddresses("1231231231234");
    	//l091.backtrack(8, new ArrayList<Integer>(), 1);
    	/*
    	for(List<Integer> l : l091.resultdot){
    		for(Integer i : l){
    			System.out.print(i);
    		}
    		System.out.println();
    	}
    	*/
    	for(String s : l091.result){
    		System.out.println(s);
    	}
    }
}
